//5,5
//2,10
//3,20
//4,30
//5,40
//5,90
// 表示有m个市民, 投票给n个店铺, 最初想的是贪心算法, 现在发现有两种可能的解法
// 第一种是纯暴力的解法, 在数据量少的时候可以, 第二种是小顶堆, 现在尝试实现小顶堆的算法
const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

class MiniTopHeap {
    constructor() {
        this.heap = []
    }

    add(obj) {
        this.heap.push(obj)
        if (this.heap.length === 1) return
        this.bubbleTop()

    }

    pickupTop() {
        if (this.heap.length === 0) return null
        if (this.heap.length === 1) return this.heap.pop()
        let temp = this.heap[0]
        this.heap[0] = this.heap.pop()
        this.downSink()
        return temp
    }

    bubbleTop() {
        let heap = this.heap
        let index = this.heap.length - 1
        let parent = Math.floor((index - 1) / 2)
        while (parent >= 0) {
            if (Object.values(heap[index])[0] < Object.values(heap[parent])[0]) {
                [heap[parent], heap[index]] = [heap[index], heap[parent]]
                index = parent
                parent = Math.floor((index - 1) / 2)
            } else {
                break
            }
        }
    }

    downSink() {
        let index = 0
        let heap = this.heap
        while (true) {
            let left = 2 * index + 1
            let right = 2 * index + 2
            let min = index
            if (left < heap.length && Object.values(heap[left])[0] < Object.values(heap[min])[0]) {
                min = left
            }
            if (right < heap.length && Object.values(heap[right])[0] < Object.values(heap[min])[0]) {
                min = right
            }
            if (min === index) {
                break
            } else {
                [heap[index], heap[min]] = [heap[min], heap[index]]
                index = min
            }
        }
    }
}


let m, n;
let initArr = [];
rl.on("line", (line) => {
    if (m === undefined) {
        [m, n] = line.trim().split(/\s*,\s*/).map(Number)
    } else {
        const [key, value] = line.trim().split(/\s*,\s*/).map(Number)
        initArr.push({[key]: value})
        if (initArr.length === m) {
            console.log(getResult(m, n, initArr))
            // clear
            m = n = undefined
            initArr.length = 0
        }
    }
})


function getResult(m, n, initArr) {
    // 首先统计每一家获取的票数
    let map = {}
    for (const obj of initArr) {
        const [[key, value]] = Object.entries(obj)
        if (!map[key]) {
            map[key] = 1
        } else {
            map[key]++
        }
    }

    // initArr 按照value值, 从小到大排序
    initArr.sort((a, b) => {
        return Object.values(a)[0] - Object.values(b)[0]
    })

    // 从队列中, 获取每个元素, 看是否满足条件
    let pq = new MiniTopHeap()
    for (const i in initArr) {
        let obj = initArr[i]
        let [[key, value]] = Object.entries(obj)
        key = key + "-" + i // 加一个角标
        pq.add({[key]: value})
    }
    // 已经获得最大票数
    let current = map[1]
    if (map[1] === undefined) {
        current = 0
    }
    let max = getMax(map)
    if (current > max) return 0

    // 需要拉票
    let ans = Infinity
    while (pq.heap.length) {
        let obj = pq.pickupTop()
        let keys = Object.keys(obj)[0].split("-")
        let index = Number(keys.pop())
        let value = Object.values(obj)[0]
        {
            // 使用
            for (const key of keys) {
                map[key]--
            }
            if (current + keys.length > getMax(map)) {
                ans = Math.min(ans, value)
            } else {
                // 尝试加入新的
                for (let i = index + 1; i < initArr.length; i++) {
                    let obj = initArr[i]
                    let [[key, val]] = Object.entries(obj)
                    key = keys.join("-") + "-" + key + "-" + i
                    pq.add({[key]: value + val})
                }
            }
            // 还原
            for (const key of keys) {
                map[key]++
            }
        }
    }
    return ans
}

function getMax(map) {
    let max = 0
    for (let key in map) {
        if (key === "1") continue
        max = Math.max(max, map[key])
    }
    return max
}